/**
 * 
 */
package datastructure;

import java.util.Iterator;
import java.util.Stack;

import tree.Node;
import utils.CreateUtils;

/**
 * @author xyyi
 * @param <E>
 *
 */
public class InOrderBinaryTreeTraversalIterator implements
		Iterator<Node<Integer>> {

	private Stack<Node<Integer>> stack = null;
	private Node<Integer> currentNode = null;

	/**
	 * 
	 */
	public InOrderBinaryTreeTraversalIterator(Node<Integer> root) {
		stack = new Stack<Node<Integer>>();
		currentNode = root;
	}

	@Override
	public boolean hasNext() {
		return !stack.isEmpty() || currentNode != null;
	}

	@Override
	public Node<Integer> next() {
		Node<Integer> node = null;
		while (hasNext()) {
			if (currentNode != null) {
				stack.push(currentNode);
				currentNode = currentNode.left;
			} else {
				node = stack.pop();
				currentNode = node.right;
				break;
			}
		}

		return node;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root = CreateUtils.bstWithTenNodes();
		InOrderBinaryTreeTraversalIterator it = new InOrderBinaryTreeTraversalIterator(
				root);
		while (it.hasNext())
			System.out.println(it.next());

	}

}
